//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-18.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

/*
 * Bellman-Ford 最短路径算法 2014-09-28 16:17:23
 */


#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#define INF 999999

/*测试数据
 
 5 5
 2 3 2
 1 2 -3
 1 5 5
 4 5 2
 3 4 3
 
*/

typedef struct path{
	int idx;
	struct path *father;
}Path;


int main(int argc, const char * argv[])
{
	int n,m;
	scanf("%d %d",&n,&m);
	
	int u[m+1],v[m+1],w[m+1];
	
	//输入边
	for (int i=1; i<=m; i++) {
		scanf("%d %d %d",&u[i],&v[i],&w[i]);
	}
	
	int dis[n+1]; //第0个点不使用
	
	//初始化
	for (int i=0; i<n+1; i++) {
		dis[i] = INF;
	}
	
	//初始化路径指针
	Path pathes[n+1];
	for (int i=0; i<=n; i++) {
		pathes[i].idx = i;
		pathes[i].father = NULL;
	}
	
	int src,dst;
	printf("输入起点终点:\n");
	scanf("%d %d",&src,&dst);
	
	dis[src] = 0; //设置dis数组起始点到起始点距离为0
	
	int bak[n+1];
	
	for (int k=0; k<n-1; k++) {//循环n-1次,因为最短路径最多包含n-1条边
		
		for (int i=1; i<=n; i++) {
			bak[i] = dis[i];
		}
		
		//松驰边
		for (int i=1; i<=m; i++) {
			
			if (dis[v[i]] > dis[u[i]] + w[i]) {
					
				dis[v[i]] = dis[u[i]] + w[i];
				
				pathes[v[i]].father = &pathes[u[i]];
			}
		}
		
		//检测是否松弛完毕, 没有值变化可以提前退出循环
		int check = 0;
		for (int i=1; i<=n; i++) {
			if (bak[i] != dis[i]) {
				check = 1;
			}
		}
		
		if (check==0) {
			break;
		}
	}
	
	
	//检测负边回路
	for (int i=1; i<=m; i++) {
		if (dis[v[i]] > dis[u[i]] + w[i]){
			printf("含有负边回路\n");
			return 0;
		}
	}
	
	
	//打印最短路径
	printf("the shortest distances are:");
	for (int i= 1; i<=n; i++) {
		printf("%d ", dis[i]);
	}
	printf("\n");
	
	printf("the shortest distance is %d \n",dis[dst]);
	printf("the shortest path is:");
	printf("%d",dst);
	
	Path *pa = pathes[dst].father;
	while (pa) {
		printf(" <- %d",pa->idx);
		pa = pa->father;
	}
	printf("\n");
	
	
	return 0;
}


